#include<iostream>
#include<vector>
#include<time.h>
#include<stack>
using namespace std;


int* PartSort(vector<int>& v,int left,int right,int pivot)
{
  int less = left - 1; 
  int more = right +1;
  int cur = left;
  while(cur < more)
  {
    if(v[cur] > pivot)
    {
      ::swap(v[--more],v[cur]);
    }
    else if(v[cur] < pivot)
    {
      ::swap(v[++less],v[cur++]);
    }
    else 
    {
      cur++;
    }
  }
  return new int[2]{less+1,more-1};
}
void QuickSort(vector<int>& v,int left,int right)
{
  if(left >= right)
  {
    return ;
  }
  //rand() % (right - left + 1) :范围: [0,right-left] 注意要加括号！！！
  ::swap(v[right],v[left + rand() % (right - left + 1)]);  //在[left,right]在一个数和right位置的元素交换
  int* equal = PartSort(v,left,right,v[right]); 
  QuickSort(v,left,equal[0]-1);
  QuickSort(v,equal[1]+1,right);
}
void QuickSortNonR(vector<int>& v,int left,int right)
{
  if(left >= right)
  {
    return ;
  }
  stack<int> st;
  st.push(left);
  st.push(right);
  while(!st.empty())
  {
    int right = st.top();
    st.pop();
    int left = st.top();
    st.pop();
    ::swap(v[right],v[left + rand() % (right - left + 1)]);
    int* equal = PartSort(v,left,right,v[right]); 
    //[left,euqal[0]-1] [equal[1] + 1,right]
    if(equal[0] - 1 > left)
    {
      QuickSortNonR(v,left,equal[0]-1);
    }
    if(right > equal[1] + 1)
    {
      QuickSortNonR(v,equal[1]+1,right);
    }
  } 
}


void MergeSort(vector<int>& v,int left,int right,vector<int>& tmp)
{
  if(left >= right)
    return ;
  int mid = (left + right) / 2;
  MergeSort(v,left,mid,tmp);
  MergeSort(v,mid+1,right,tmp);

  int begin1 = left,end1= mid;
  int begin2 = mid+1,end2 = right;
  int index = left;
  while(begin1 <= end1 && begin2 <= end2)
  {
    if(v[begin1] < v[begin2])
      tmp[index++] = v[begin1++];
    else 
      tmp[index++] = v[begin2++];
  } 
  while(begin1<=end1)
    tmp[index++] = v[begin1++];
  while(begin2 <= end2)
    tmp[index++] = v[begin2++];

  for(int i = left;i<=right;i++)  
    v[i] = tmp[i];
}

void AdjustUp(vector<int>& v,int child)
{
  int parent = (child-1)/2;
  while(child > 0)
  {
    if(v[child] > v[parent])
    {
      ::swap(v[child],v[parent]);
      child = parent;
      parent = (child-1)/2;
    }
    else 
      break;
  }
}
void AdjustDown(vector<int>& v,int parent,int n)
{
  int child = parent*2+1;
  while(child < n)
  {
    if(child + 1 < n && v[child+1] > v[child])
      child += 1;
    if(v[child] > v[parent])
    {
      ::swap(v[child],v[parent]);
      parent = child;
      child = parent*2+1;
    }
    else 
      break;
  }
}
//排升序->建大堆
void HeapSort(vector<int>& v)
{
  int n = v.size();
  //从最后一个叶子节点的父节点开始向下调整建堆
  // for(int i = (n-1-1)/2;i>=0;i--)
  //   AdjustDown(v,i,n);
  
  //第一个节点先认为是堆，然后从第二个节点开始向上调整建堆
  for(int i = 1;i<n;i++)
    AdjustUp(v,i);
  int end = n - 1;
  while(end > 0)
  {
     swap(v[0],v[end]);
     AdjustDown(v,0,end);
     end--;
  }
}

void BubbleSort(vector<int>& v)
{
  //n个元素只需排序n-1趟
  int n = v.size();
  for(int i = 0;i<n-1;i++)
  {
    bool flag = true;
    for(int j = 0;j<n - 1 - i;j++)
    {
      if(v[j] > v[j+1])
      {
        ::swap(v[j],v[j+1]);
        flag = false;
      }
    }
    if(flag) break;
  }
}

void CountSort(vector<int>& v)
{
  int max_val = v[0];
  for(int i = 0;i<v.size();i++)
    if(v[i] > max_val)
      max_val = v[i];
  
  int* CountArr = new int[max_val];
  for(int i = 0;i<v.size();i++)
    CountArr[v[i]]++;
 
  int index = 0;
  for(int i = 0;i<max_val;i++)
  {
    while(CountArr[i] > 0)
      v[index++] = i,CountArr[i]--;
  }
}

void CountSort_version2(vector<int>& v)
{
  int max_val = v[0],min_val = v[0]; 
  for(int i = 1;i<v.size();i++)
  {
    if(v[i]>max_val) max_val = v[i];
    if(v[i] < min_val) min_val = v[i];
  }

  int gap = max_val - min_val + 1;
  int* tmp = new int[gap];
  for(int i = 0;i<v.size();i++)
  {
    tmp[v[i] - min_val]++;
  }
  int index = 0;
  for(int i = 0;i<gap;i++)
  {
    while(tmp[i] > 0)
    {
      v[index++] = i + min_val;
      tmp[i]--;
    }
  }
}



void SelectSort(vector<int>& v)
{
  int n = v.size();  
  int end = n -1;
  while(end > 0)
  {
    int maxi = 0;
    for(int i = 0;i<=end;i++)
    {
      if(v[i] > v[maxi]) maxi = i;
    }
    swap(v[maxi],v[end]);
    end--;
  }
}

void SelectSort(vector<int>& v)
{
  int n = v.size();
  int begin = 0,end = n - 1; 
  while(begin < end)
  {
      int maxi = begin,mini = begin;
      for(int i = begin;i<=end;i++)
      {
        if(v[maxi] < v[i]) maxi = i; 
        if(v[mini] > v[i]) mini = i;
      }
      //将maxi和end位置的值交换,mini的值和begin的值交换
      
      swap(v[begin],v[mini]);
      if(maxi == begin) maxi = mini;
      swap(v[maxi],v[end]);
      begin++,end--;
  }
}

void InsertSort(vector<int>& v)
{
  int n = v.size();
  for(int i = 0;i<n-1;i++) //注意i的范围是<n-1
  {
    //将x插入到[0,end]的有序区间
    int end = i;
    int x = v[end+1]; 
    while(end >= 0)
    {
      if(v[end] > x)
        v[end+1] = v[end],end-=1;
      else 
        break;
    } 
    v[end+1] = x;
  }
}
void ShellSort(vector<int>& v)
{
  int n = v.size();
  int gap = n;
  while(gap > 1)
  {
    gap = gap / 2; //gap = gap / 3 + 1
    //多组一锅炖
    for(int i = 0 ; i < n - gap ;i++)
    {
      int end = i;
      int x = v[end+gap];
      while(end >= 0)
      {
        if(v[end] > x)
        {
          v[end+gap] = v[end];
          end -= gap;
        }
        else 
          break;
      }
      v[end+gap] = x;
    }
  }
  // 方法2:每一组分别预排序
  //for(int j = 0 ; j < gap ;j++)
  //{
  //  //注意：当前组的起点是j
  //  for(int i = j;i<n-gap;i+=gap)
  //  {
  //    //.....
  //  }
  //}
}
